package com.txy.alth.dp;

/**
 * 01背包
 * 每件物品只能取1份，必须整取
 *
 * dq方程 dq[i,j]  i是第i件物品 j是最大承重
 * 如果
 *  不可用选这件物品 j<w[i]
 *  则 dq[i,j]=dq[i-1,j]
 *
 *  可以选这件物品
 *      不选 dq[i,j]=dq[i-1,j]
 *      选了 dq[i,j]=v[i]+dq[i-1,j-w[i])
 *      所以 dq[i,j] = max(dq[i-1,j], v[i]+dq[i-1,j-w[i]))
 */
public class Bag {
    public static int maxValue(int[] values, int[] weights, int capacity) throws Exception {
        checkParam(values, weights, capacity);
        int[][] dp = new int[values.length+1][capacity+1];
        for(int i=1;i<=values.length;i++) {
            for(int j=1;j<=capacity;j++) {
                if(j<weights[i-1]) // 承重小于当前物品，肯定不能选该物品
                    dp[i][j]=dp[i-1][j];
                else // 能选该物品时，在选和不选两种结果间取最大值
                    dp[i][j]= Math.max(dp[i-1][j], values[i-1]+dp[i-1][j-weights[i-1]]);
            }
        }
        return dp[values.length][capacity];
    }
    private static void checkParam(int[] values, int[] weights, int capacity) throws Exception {
        if(values == null || values.length == 0 || weights == null || weights.length == 0 || values.length!=weights.length || min(weights) > capacity) throw new Exception("参数不合法");
    }
    private static int min(int[] weights) {
        int min = Integer.MAX_VALUE;
        for(int w : weights) {
            if(w<min) min = w;
        }
        return min;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(maxValue(new int[]{6,3,5,4,6}, new int[]{2,2,6,5,4}, 10));
    }
}
